import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/4 15:09
 * @description 动态规划 dp[i][j]表示从数组【0，i】下标范围内选取若干个整数，是否存在一种选取方案使得被选取的正整数和 = j。
 * 初始情况，边界dp[i][0] = true, 因为不选取任何整数，那么被选取的整数和为 0，符合条件
 * dp[0][nums[0]] = true, 当只剩下一个整数时，那么只有nums[0]可以被选取，dp[0][nums[0]] = true;
 */
public class Solution {
    public static void main(String[] args) {

    }
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return false;
        }
        int sum = 0, maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        if (maxNum > target) {
            return false;
        }
        boolean[][] dp = new boolean[n][target + 1];
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
        }
        dp[0][nums[0]] = true;
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            for (int j = 1; j <= target; j++) {
                if (j >= num) {
                    // j >= num时，可以选择nums[i],也可以不选取，两者有一个符合条件，那么dp[i][j] = true;
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
                } else {
                    // j < num时，在选取的数字和为j时，无法选取当前数字，
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n - 1][target];
    }

}
